UVa/11665 - Chinese Ink/11665.2.cpp

   1 // Accepted
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define D(x) cout << #x " is " << x << endl
  27
  28 #define EPS 1e-9
  29
  30 typedef pair<int, int> point;
  31 typedef vector< point > polygon;
  32
  33 vector< polygon > polygons;
  34
  35 const int MAXN = 50;
  36 int p[MAXN];
  37
  38 int find(int u) {
  39     return p[u] == u ? u : p[u] = find(p[u]);
  40 }
  41
  42 void link(int u, int v) {
  43     if (find(u) != find(v)) {
  44         p[find(u)] = find(v);
  45     }
  46 }
  47
  48 // Polar angle
  49 // Returns an angle in the range [0, 2*Pi) of a given Cartesian point.
  50 // If the point is (0,0), -1.0 is returned.
  51 // REQUIRES:
  52 // include math.h
  53 // define EPS 0.000000001, or your choice
  54 // P has members x and y.
  55 double polarAngle( point p ) {
  56     double x = p.first, y = p.second;
  57     if(fabs(x) <= EPS && fabs(y) <= EPS) return -1.0;
  58     if(fabs(x) <= EPS) return (y > EPS ? 1.0 : 3.0) * acos(0);
  59     double theta = atan(1.0 * y / x);
  60     if(x > EPS) return(y >= -EPS ? theta : (4*acos(0) + theta));
  61     return(2 * acos( 0 ) + theta);
  62 }
  63
  64 //Point inside polygon
  65 // Returns true iff p is inside poly.
  66 // PRE: The vertices of poly are ordered (either clockwise or
  67 //      counter-clockwise.
  68 // POST: Modify code inside to handle the special case of "on
  69 // an edge".
  70 // REQUIRES:
  71 // polarAngle()
  72 // include math.h
  73 // include vector
  74 // define EPS 0.000000001, or your choice
  75 bool pointInPoly( point p, const polygon &poly ) {
  76   int n = poly.size();
  77   double ang = 0.0;
  78   for(int i = n - 1, j = 0; j < n; i = j++){
  79     point v( poly[i].first - p.first, poly[i].second - p.second );
  80     point w( poly[j].first - p.first, poly[j].second - p.second );
  81     double va = polarAngle(v);
  82     double wa = polarAngle(w);
  83     double xx = wa - va;
  84     if(va < -0.5 || wa < -0.5 || fabs(fabs(xx)-2*acos(0)) < EPS){
  85         // POINT IS ON THE EDGE
  86         return true;
  87         assert( false );
  88         ang += 2 * acos( 0 );
  89         continue;
  90       }
  91     if( xx < -2 * acos( 0 ) ) ang += xx + 4 * acos( 0 );
  92     else if( xx > 2 * acos( 0 ) ) ang += xx - 4 * acos( 0 );
  93     else ang += xx;
  94   }
  95   return( ang * ang > 1.0 );
  96 }
  97
  98
  99 /*
 100   Returns true if point (x, y) lies inside (or in the border)
 101   of box defined by points (x0, y0) and (x1, y1).
 102 */
 103 bool point_in_box(double x, double y,
 104                   double x0, double y0,
 105                   double x1, double y1){
 106   return
 107     min(x0, x1) <= x && x <= max(x0, x1) &&
 108     min(y0, y1) <= y && y <= max(y0, y1);
 109 }
 110
 111
 112 /*
 113   Returns the cross product of the segment that goes from (x1, y1) to (x3, y3)
 114   with the segment that goes from (x1, y1) to (x2, y2)
 115 */
 116 int direction(int x1, int y1, int x2, int y2, int x3, int y3) {
 117     return (x3 - x1) * (y2 - y1) - (y3 - y1) * (x2 - x1);
 118 }
 119
 120 /*
 121   Finds the intersection between two segments (Not infinite
 122   lines!)
 123   Segment 1 goes from point (x0, y0) to (x1, y1).
 124   Segment 2 goes from point (x2, y2) to (x3, y3).
 125
 126   (Can be modified to find the intersection between a segment
 127   and a line)
 128
 129   Handles the case when the 2 segments are:
 130   *Parallel but don't lie on the same line (No intersection)
 131   *Parallel and both lie on the same line (Infinite
 132   *intersections or no intersections)
 133   *Not parallel (One intersection or no intersections)
 134
 135   Returns true if the segments do intersect in any case.
 136 */
 137 bool segment_segment_intersection(int x1, int y1,
 138                                   int x2, int y2,
 139
 140                                   int x3, int y3,
 141                                   int x4, int y4){
 142
 143     int d1 = direction(x3, y3,   x4, y4,   x1, y1);
 144     int d2 = direction(x3, y3,   x4, y4,   x2, y2);
 145     int d3 = direction(x1, y1,   x2, y2,   x3, y3);
 146     int d4 = direction(x1, y1,   x2, y2,   x4, y4);
 147     bool b1 = d1 > 0 and d2 < 0 or d1 < 0 and d2 > 0;
 148     bool b2 = d3 > 0 and d4 < 0 or d3 < 0 and d4 > 0;
 149     if (b1 and b2) return true;
 150     if (d1 == 0 and point_in_box(x1, y1,     x3, y3, x4, y4)) return true;
 151     if (d2 == 0 and point_in_box(x2, y2,     x3, y3, x4, y4)) return true;
 152     if (d3 == 0 and point_in_box(x3, y3,     x1, y1, x2, y2)) return true;
 153     if (d4 == 0 and point_in_box(x4, y4,     x1, y1, x2, y2)) return true;
 154     return false;
 155 }
 156
 157 bool polygonsIntersect(const polygon &a, const polygon &b) {
 158     int na = a.size(), nb = b.size();
 159     for (int i = 0; i < na; ++i) {
 160         if (pointInPoly(a[i], b)) return true;
 161     }
 162     for (int i = 0; i < nb; ++i) {
 163         if (pointInPoly(b[i], a)) return true;
 164     }
 165
 166     for (int i = 0; i < na; ++i) {
 167         for (int j = 0; j < nb; ++j) {
 168             int xa1 = a[i].first, ya1 = a[i].second;
 169             int xa2 = a[(i + 1) % na].first, ya2 = a[(i + 1) % na].second;
 170             int xb1 = b[j].first, yb1 = b[j].second;
 171             int xb2 = b[(j + 1) % nb].first, yb2 = b[(j + 1) % nb].second;
 172             if (segment_segment_intersection(xa1, ya1,    xa2, ya2,               xb1, yb1, xb2, yb2)) {
 173                 return true;
 174             }
 175         }
 176     }
 177
 178
 179     return false;
 180 }
 181
 182
 183 void solve() {
 184     int n = polygons.size();
 185     for (int i = 0; i < n; ++i) {
 186         p[i] = i;
 187     }
 188
 189     for (int i = 0; i < n; ++i) {
 190         for (int j = i + 1; j < n; ++j) {
 191             if (polygonsIntersect(polygons[i], polygons[j])) {
 192                 link(i, j);
 193             }
 194         }
 195     }
 196     set<int> ans;
 197     for (int i = 0; i < n; ++i) {
 198         ans.insert(find(i));
 199     }
 200     cout << ans.size() << endl;
 201 }
 202
 203
 204 int main(){
 205     int n;
 206     while (cin >> n) {
 207         if (n == 0) break;
 208         string s; getline(cin, s);
 209         polygons.clear();
 210         for (int i = 0; i < n; ++i){
 211             polygons.push_back(polygon());
 212             getline(cin, s);
 213             stringstream sin(s);
 214             int x, y;
 215             while (sin >> x >> y) {
 216                 polygons.back().push_back(point(x, y));
 217             }
 218             assert(polygons.back().size() >= 3);
 219         }
 220         assert(polygons.size() == n);
 221
 222         solve();
 223     }
 224     return 0;
 225 }